package lc20240423;

import java.util.*;

public class RandomizedSet {
    List<Integer> nums;
    Map<Integer,Integer> indices;
    Random random;

    public RandomizedSet(){
        nums=new ArrayList<>();
        indices=new HashMap<>();
        random=new Random();
    }

    public boolean insert(int val){
        if (indices.containsKey(val)) {
            return false;
        }
        int index = nums.size();
        nums.add(val);
        indices.put(val, index);
        return true;
    }
    public boolean remove(int val){
        if (!indices.containsKey(val)){
            return false;
        }
        //获取val所在位置索引
        int index=indices.get(val);
        //获取最后一个索引的元素
        int last=nums.get(nums.size()-1);
        nums.set(index,last);
        indices.put(last,index);
        nums.remove(nums.size()-1);
        indices.remove(val);
        return true;
    }

    public int getRandom(){
        int randomIndex=random.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}
